package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode0031 
* @author      : ganwei 
* @date        : 2020年5月13日 
* @Description : leetcode 31. 下一个排列 
*/
public class Leetcode0031 {
	/**
	 * -解题思路，从数学分析的角度
	 */
    public void nextPermutation(int[] nums) {
    	int i = nums.length-2;
    	while(i >= 0 && nums[i+1] <= nums[i]) {
    		i--;
    	}
    	if(i >= 0) {
    		int j = nums.length-1;
    		while(nums[i] >= nums[j]) {
    			j--;
    		}
    		swap(nums,i,j);
    	}
    	reverse(nums, i+1);
    }
    
    public void reverse(int[] nums, int start) {
    	int i = start, j = nums.length - 1;
    	while(i < j) {
    		swap(nums, i, j);
    		i++;
    		j--;
    	}
    }
    
    public void swap(int[] nums, int i, int j) {
    	int tmp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = tmp;
    }
    
    public static void main(String[] args) {
    	Leetcode0031 l0031 = new Leetcode0031();
    	int[] nums = {1,2,3,4,5};
    	l0031.nextPermutation(nums);
    	
    	for(int i : nums) {
    		System.out.println(i);
    	}
    	
    }
}
